#include <vector>
#include <string>
#include <stdexcept>
#include <iostream>
#include <codecvt>
#include <locale>
#include "strlib.hpp"
#include "main.hpp"

using namespace std;

vector<string> split(string input, string delimiter) {
  vector<string> result;
  int dLen = delimiter.size();
  int lastFound = 0;
  int found = input.find(delimiter, lastFound);
  while(found != string::npos) {
    found = input.find(delimiter, lastFound);
    result.push_back(input.substr(lastFound, found - lastFound));
    lastFound = found + dLen;
  }
  if(result.size() == 0) {
    result.push_back(input);
  }
  return result;
}

int minOfThree(int a,int b, int c) {
  if (a < b && a < c) {
    return a;
  } else if(b < a && b < c) {
    return b;
  } else {
    return c;
  }
    
}

wstring getSubString(wstring str, int pos, int size) {
  wstring result;
  try {
    result = str.substr(pos, size);
  }
  catch(out_of_range e) {
    result = L"";
  }
  return result;
    
  
}

wstring strToWstr(string input) {
  std::wstring_convert<std::codecvt_utf8_utf16<wchar_t>> converter;
  return converter.from_bytes(input);  
}

int editDistance(string i1, string i2) {
  wstring a = strToWstr(i1);
  wstring b = strToWstr(i2);  
  int size = (a.size() < b.size() ? b.size() : a.size());
  int matrix[size + 1][size + 1];
  int val = 0;
  for(int x = 0; x < size + 1; x++) {
    if(getSubString(a, x - 1) != L"") {
      val++;
    }
    matrix[x][0] = val; 
  }
  val = 0;
  for(int y = 0; y < size + 1; y++) {
    if(getSubString(b, y - 1) != L"") {
      val++;
    }
    matrix[0][y] = val; 
  }

  for(int x = 1; x < size + 1; x++) {
    for(int y = 1; y < size + 1; y++) {
      int mod = 1;
      if(getSubString(a, x - 1) == getSubString(b, y - 1)) {
        mod = 0;
      }
      matrix[x][y] = minOfThree(matrix[x - 1][y], matrix[x][y - 1], matrix[x - 1][y -1]) + mod;
    }
  }
  if(debugEnabled) {
    cout << "a size: " << a.size() << "; b size: " << b.size() << "\n";
    wcout << "  " << a << "\n";
    for(int y = 0; y < size + 1; y++) {
      wstring substring = getSubString(b, y - 1);
      wcout << (substring == L"" ? L" " : substring);
      for(int x = 0; x < size + 1; x++) {
        wcout << matrix[x][y];
      }
      wcout << "\n";
    }
  }
  return matrix[size][size];
}

float compareStrings(string a, string b) {
  wstring wa = strToWstr(a);
  wstring wb = strToWstr(b);  
  int max = (wa.size() >= wb.size() ? wa.size() : wb.size());
  return ((float)max - (float)editDistance(a,b)) / (float)max;
}
